<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
<html>
<head>
<title>CS45: Lab 4</title>

<style type="text/css">
@import url("style/stylesheet_hw.css");
</style>
</head>

<body> 
<div id="Wrapper"> 
  <div id="HeadImgMed"> 
    <div id="HeaderSmall">
	    <h1>CS45 Lab 4: Paging Experiments</h1>
	  </div>
	  <div class="TagLine">
           <b>Code Due: Sunday April 6 before 11:59pm</b>
           <br><b>Report Due: Wednesday  April 9 at the beginning of class</b>
	  </div>
  </div> <!--Header image box-->
     
  <div id="Content">

<p>
<b>Content:</b>
<ul>
<li><A HREF="#intro">Problem Introduction</A>
<li><A HREF="#details">Part 1: System call Implementation Details</A>
<li><A HREF="#expr">Part 2: Experiments and Report</A>
<li><A HREF="#util">Useful Unix Utilities</A>
<li><A HREF="#latex">Latex: Word processing like a Computer Scientist</A>
<li><A HREF="#handin">What to Hand in</A>
<li><A HREF="#demo">Demo</A>
</ul>

<div class="TagLine" id="intro">Problem Introduction</div>

This assignment is a study of Linux's implementation of virtual memory.
It is a two part assignment, the first part involves implementing a 
simple system call to obtain page fault statistics for individual processes, 
groups of processes, and for the system as a whole.  The second part 
involves evaluating Linux's page replacement policy using your 
system call (and other utilities) to obtain performance measures of workload
tests you design and run.  You will write a 3-5 page report describing your experiments and results.
<p>
This project requires a fair amount of time in designing, writing,  
and running user-level experiments, and very little time writing and
testing your system call.  I'd recommend leaving yourself at least one 
full week, and better yet, 1.5 weeks, for designing, writing, and 
running experiments and for writing your final report.

<br>
<br>
<div class="TagLine" id="details">Project Details
<br>Part 1: Adding a new system call
</div>
Start by setting up a <a href="http://www.cs.swarthmore.edu/~newhall/cs45/s14/Labs/git_setup.html">git repo</a> for your lab 4 work (remember to add three
users: you, partner, and your shared cs45X user).  Then, copy over
my starting point files and add them to your repo:
<pre>
cp ~newhall/public/cs45/lab04/* .
</pre>
The starting point contians files with #includes and a Makefile for a
test program.
<p>
Implement a new system call:
<pre>int pgfltstats(pid_t pid, int flag, pf_info_struct *info)</pre>   
<p>
The <code>pf_info_struct</code> should contain fields for:
<ol>
<li> total number of minor page faults 
<li> total number of major page faults 
<li> number of processes included in these counts
</ol>
<p>   
If <code>pid</code> is:
<ul>
<li> <b>-1</b>: then return total count statistics for all processes 
in the system.
<li> <b>positive</b> then look at the flag field and do the following: 
  <ol>
  <li> flag is PGFLTSTAT_PROC: then return count statistics for the
       single process with the matching pid   
  <li> flag is PGFLTSTAT_OWNER: then return the total count statistics for
    all process in the system with the same owner (uid) as the specified pid.
    Use the <tt>real_cred</tt> field in the task_struct to find the owner's
    uid value.  
  </ol>
</ul>
<p>
You can use fields in task_struct for obtaining the values you need.
Make sure to check for error conditions and return 
appropriate error values as in the previous assignments. 
<p>
<p>
You can use <tt>vmstat</tt>, <tt>ps</tt> and <tt>/proc/pid/</tt> files to help 
you determine if your system call is implemented correctly (look at 
vmstat, ps, and proc man pages for more info).  Here is an example of 
printing out the uid of every process in the system, and then sorting 
the results by pid:
<pre>
ps axo pid,ruid,time,cmd | sort -k 2
</pre>
You may also want to use your procinfo system call from lab 2 (perhaps 
modifying it to include <tt>uid</tt> information).  

<br>
<br>
<div class="TagLine" id="expr">Part 2: Experiments Testing the VM system 
and a Written Report</div>
For this part, you will use your system call (and other utilities)
to collect information about page faults and other performance data
for different programming loads. I want you to (through experiments) 
determine what page replacement algorithm Linux likely implements.  
I'm sure you can figure out what Linux's page replacement policy is 
just by reading Linux documentation and/or reading Linux source code. 
However, the point of this assignment is to see if you can verify 
experimentally what you know (or suspect) about Linux's page replacement
policy.
<p>
Kernel code you may want to browse:
<ul>
<li> page fault handling routines in 
<tt>arch/x86/mm/fault.c</tt> and <tt>mm/memory.c</tt>
<li> page replacement code in <tt>mm/vmscan.c</tt>, which begins 
with <tt>try_to_free_pages</tt>. 
</ul>
<p>
Think about running experiments to answer the questions about how 
the policy works for different types of workloads, and what that 
tells you about the policy.  In designing your experiments, you should 
write user-level test programs that access memory in different patterns, 
and run different experiments using them to collect performance data to 
help you answer questions like:
<ol>
<li> When does Linux's page replacement policy work well 
     (what types of workloads)? 
<li> When does it not work well?  
<li> How well does it work for a mixed workload?
<li> etc.
</ol>
And what do the answers to these questions tell you about Linux's page
replacement policy?  For example try and answer questions like: 
<ol>
<li>is it most like FIFO?  
<li> or MRU?  
<li> or LRU?  
<li> or Working Set? 
<p>Why or why not?  And, in what way(s)?  
</ol>
The idea is to design experiments that support your answers to these
questions.
<p>
<h3>Getting Started With Testing</h3>
To get started, you will likely want to read kernel code and 
other Linux documentation to help you develop some initial hypotheses.  
You can test negative hypotheses as well as positive ones (i.e. "I don't 
think Linix implements the X policy, and I'm going to test this by ..."),
but you should have some positive hypotheses as well; there is a difference 
between negative hypotheses that can help support your positive ones, 
and bad hypotheses (and bad experiments) that don't really show anything.
<p>
Next,think about how to design experiments to test your hypotheses:
<ul>
<li> You will want to write some user-level test programs that allocate 
     memory and access it repeatedly in some pattern (you need to allocate 
     enough memory to cause page faults).  
     <p>
     Try to write very simple test programs; complicated test programs
     often complicate what they are testing, and simple test programs often
     clearly test what you think they are testing.
<p>
<li> Use these test programs to design and run experiments to help 
     support (or refute) your hypotheses.  
</ul>
<p>
Look at the details in the Report section below to help guide your 
hypothesis and experiments design and testing.
<p>
To write test programs that use enough memory to trigger paging, look at
the <tt>/proc/meminfo</tt> file.  This give the total amount of 
free memory (MemFree, in Kbytes).  If you are running an experiments,
make sure the the process(es) allocate enough memory to trigger page
replacement (they need to allocate enough virtual memory space so that 
it won't all fit into free physical memory).  However, be careful that you 
do not allocate too much memory, otherwise, you can run out of swap space 
and the kernel will start killing process.  The amount of free swap space 
can be found in <tt>/proc/meminfo</tt> (SwapFree, in Kbytes).
<p>
<font color="red">Note:</font> it will take several rounds of trial and
error to get your experiments set so that they are really testing the
thing you want to test.  As a result, start early, run some initial 
tests, see what they show (or don't show) and then re-design to get
tests that show what you want.
<p>
Also, <b>each individual experiment should be run several times</b>; a single 
run of an experiment is not definitive.  You should run several iterations
of each experiment and take the average (and compute stddev) over this set.   
<p>
You may also want to periodically re-boot 
and start with a clean system from time to time as you go: RAM will get
warmed up after the first run of something (the a.out file can still 
be in RAM from the previous run), and this may or may not be important
to your experiments.

<h3>Report</h3>
You should write 3-5 page report (do not give me anything longer than 
5 pages) describing your experiments and results.  
<p>
In particular, your report should have the following:
<ol>
<li> Introduction.  Describe at a high-level what you are 
doing and why, and describe what your high-level hypothesis is 
(i.e. "We started out guessing that Linux's page replacement policy is X, 
but our experiments will show that it is in fact, more like Y" or 
"we start out making no assumptions about Linux's page replacement policy, 
and our experiments will answer the question of is it more like X, Y or Z.").
<p>
<li> Short paragraph describing how you implemented your system call 
     to get get per-process, per-owner, and system wide page fault counts?
     Also, describe other Unix utilities you used to collect performance data
     for your experiments.
<p>
<li> Main part:  describe your experiments and results:
For each experiment, you should:
<ol>
<li> Clearly state what your hypothesis is 
     <br>(i.e. "Application that does X should be a bad/good 
     case for Linux's page replacement policy because ...)
<li> Explain how your experiment is testing that hypothesis
     <br>(We are testing this hypothesis by running application P, which 
     does ..., N times on and collecting X,Y, and Z metrics using our 
     system call, vmstat, time,...  With these measures, we can see 
     whether or not ... because ...).  
<li> Present your Results.  
<li>  Explain your results!
      <br>(Our results show that ...   This does/does not match our expected
       result, because ...   (if it doesn't, think about some other tests
       you could run to explain why it doesn't, or look for data you do
        have to explain it)
</ol>
<b>Quality of Experiments is much, much better than quantity; a few well thought
out and well done experiments is sufficient. </b>
<p>
<li> Conclusion. It should include a statement of the major result(s)
     of your experiments (which policy(ies) is Linux's most like? and in what
     way(s)?).  Also, tell me what you found to be the most difficult part
     of the hypothesis testing phase of this assignment.
</ol> 

<br>
<br>
<div class="TagLine" id="util">Some useful system calls and utilities for testing purposes</div>
<ul>
<li><b><tt>sleep(val)</tt> </b>make program block for val seconds
<li><b><tt>usleep(val)</tt> </b>make program block for val micro seconds
<li><b><tt>clone</tt> </b>create a kernel level thread
<br>you can also write a pthreads program to create threads.  See my
documentation about <a href="http://www.cs.swarthmore.edu/~newhall/unixlinks.html#pthreads">pthread programming</a> and pthreads man pages.
<li><b><tt>fork</tt> </b>you know what this does

<p>
<li> your system call
<li> your system calls from previous labs (Events or procinfo may be useful
for testing or for use in test programs you write).
<li><b><tt>time a.out</tt></b> times the execution of the a.out file
<li><b><tt>vmstat</tt></b>: prints out statistics about the VM system. This may 
help you in verifying that your system call is implemented correctly 
(vmstat alone is  not enough to do your testing...you need your system call).  
<tt>'vmstat -n 1'</tt></b> prints out vmstat statistics every 1 second.
<li><b><tt>watch -n X [command]</tt></b>: every X seconds execute command.  For 
example, to print out the contents of the stat file for process 22832 every 1 
second I'd do the following:
<pre>
	watch -n 1 cat /proc/22832/stat
</pre>
<li> <b><tt>/proc</tt></b>: file system interface to processes.  You can
read (and write) variables in a process' address space (I'd recommend
never writing).
<ul>
<li> in <b><tt>/proc/sys</tt></b> is the /proc interface to the
kernel.  By <tt>cat</tt>'ing files in these subdirectories, you can 
read kernel statistics.  
<li> in <b><tt>/proc/[pid]</tt></b> directories are the /proc interface to
individual processes in the system.  Again you can <tt>cat</tt> the
contents of files in these directories to get per-process statistics.
<li> <b><tt>/proc/meminfo</tt></b>
<li> <b><tt>/proc/vmstat</tt></b>: system-wide VM information
<li> <b><tt>/proc/swaps</tt></b>: prints out the current amount of 
swap space in use.  You can cat this out to see if your experiments
are triggering swapping.  In Linux, only pages that are written to
are swapped out (like stack, heap or global space).  Pages of instructions
(.text) are paged in from the file system and not to/from swap.
<p>
</ul>
<li> <a href="http://web.cs.swarthmore.edu/~newhall/unixlinks.html#exper">tools for running experiments</a> using screen, script, and writing 
<a href="http://www.cs.swarthmore.edu/~newhall/unixlinks.html#shell">bash scripts to run a set of experiments</a>.  You can also write some simple python scripts to process post experiment output in a typescript file, for example.  As
you write bash scripts to run large sets of experiments, keep this post
processing in mind (you may want to echo out some state periodically to
make it easier to write such a post processing script). 
<p>
<li> You will also likely want to run <a href="http://www.cs.swarthmore.edu/~newhall/unixhelp/virtualbox_lab2.php#starting">virtualbox in non-gui mode</a> 
so that you can start up a bunch of experiments, logout, and then come back 
later to see how they worked out.
</ul>

<br>
<br>
<div class="TagLine" id="latex">Latex</div>

You can use any word processing software you'd like to write your
report.  However, if you want to learn latex (word processing
the Unix way), there are some starting points for a report
(paper) and a report using bibtex for references (bibtex) in
the following directory:
<pre>
/home/newhall/public/latex_examples
</pre>
<p>
For this assignment, the example in the <tt>paper</tt> subdirectory
is likely a good starting point.  In the paper subdirectory is an
README file with information on how to create a .dvi .ps and .pdf
file from the latex source file (example.tex).  In addition, 
there is a makefile that contains rules for building all of 
these.  The example.tex file, contains examples of importing
postscript figure files, creating sections and subsections, using 
different fonts, creating lists, and referencing figures within
a document. Probably the easiest thing to do is to grab the contents 
of this directory as a starting point for your report, then edit example.tex 
with your report.
<p>
Also, off my Unix and C help pages, I have much more documentation 
about creating documents, and figures, graphs:
<a href="http://web.cs.swarthmore.edu/~newhall/unixlinks.html#doc">
Tools for Documents and Figures</a>

<br>
<br>
<div class="TagLine" id="handin">Submit</div>
<ol>
<li> <b>Code:</b> using <a href="../../howto_runninghandin.html">cs45handin</a>,
 submit a tar ball with the following:
     <ol>
     <li> README file with (1) your names, (2) how many late days you 
          have used on this assignment, and how many you have used total, 
	  (3) a description of how to run your test programs (show 
	  example command lines, or how to run bash scripts).
     <li> copies of all .c and .h files you added or modified in the kernel
          to implement your system call
     <li> copies of all your test programs used in experiments,
          and the test program you used to test your system call
	  for correctness.
          <p>
          also include any bash scripts you wrote for running experiments.
     </ol> 
<p>
<li> <b>Report:</b> turn in <b>a hardcopy</b> of your report in class on 
     the same day that you submit your tar ball.  You should also email 
     me a pdf file; but I want a print out handed in in class too.
     <p>
     <font color="red">NOTE:</font>
     If you turn in your report later than the beginning of class on the 
     due date, then  your assignment is late (even if your tar ball 
     was submitted before the due date).
</ol>
<br>
<br>
<h3 id="demo">Demo</h3>

You and your partner will sign up for a 20 minute demo slot.  You should show
me that your system call is correct, robust, and implements all required 
features (and think about verification of this to demo me).  In addition, 
I'd like to see you run one or more of your test programs that you ran 
as part of your experiments.  

</div> <!--content--> 
<div id="Footer">
<p>
<!--Common footer text/images-->
<br>
<small>
<!--File/php last-edited time stamping-->
Last updated: Thursday, April 03, 2014 at 07:50:50 PM</small>
</div>
</div> <!--wrapper-->

